1. Field of the Invention
This invention relates to computer local area networks and in particular to a method and apparatus for enforcing valid network topologies.
2. Description of the Related Art
Local area networks (LANs) interconnect a collection of stations for the purpose of exchanging information over a communications channel. LANs that cover extended distances and/or are based on fiber optics may configure a "ring" from a number of individual point to point physical connections between the stations comprising the network to form the communication channel. Such rings are exemplified by the FDDI (Fiber Distributed Data Interface) proposed by American National Standards Institute (ANSI) and IEEE standard 802.5-1985 "American National Standard for Token Ring Access Method," ANSI X3.139-1987, "Fiber Distributed Data Interface Media Access Control (MAC)," and ANSI X3.148-1988, "Fiber Distributed Data Interface Physical Layer Protocol (PHY)."
Double loop rings are often configured rather than single loop rings. In a double loop ring, each ring in fact consists of a primary and a secondary ring. The stations, or nodes, making up the LAN may be combinations of single attachment stations (SAS) 10 of FIG. 1A, having a single physical attachment point (which includes the media, or the hardware comprising the communication link to an adjacent station), dual attachment stations (DAS) 12 of FIG. 1B, having two attachment points, wire concentrators (WC) 14 of FIG. 1C, having many attachment points, and combination DAS/WC stations 16 of FIG. 1D having two attachment points on the DAS side and several attachment points on the WC side and internal connections (not shown) between the WC and the DAS. Each connection between two station attachment points is called a Physical Connection (PC) and has two physical links which carry signals in opposite directions and from which the LAN communications channel is configured. The communications channel may be configured as a physical loop with "trees" branching to stations not on the ring. In normal operation, the two rings are often formed into one ring, which will be called the primary ring.
An example of a LAN configured as a ring of trees of the above mentioned station types is shown by LAN 20 of FIG. 2. The two physical links of each PC are connected to other PC's to provide two rings, a primary ring 22 and a secondary ring 24. Use of two rings ensures tolerance to station or channel failure as explained by Rom et al. in "A Reconfiguration Algorithm for a Double-Loop Token-Ring Local Area Network," IEEE Transactions on Computers, Vol 37, No. 2, February 1988. The network automatically reconfigures to eliminate the failed element and resume operation, as shown by LAN 50 of FIG. 3 where loopbacks 54 and 58 "heal" the ring and permit continued operation by the attached stations.
LAN stations may conform to the reference model Open Systems Interconnection (OSI) which calls for a layered station organization as proposed by the International Standards Organization and described by A. S. Tanenbaum in "Computer Networks," Prentice Hall, Inc., 1981, pages 16-21. Each station contains a Physical (PHY), Data Link, Network, Transport, Session, Presentation, and Application layer.
PHY provides electrical and/or optical connections, encodes and decodes the signals for all higher layers, and essentially supports a communication channel from one station to another and transmits and receives data to and from the PHY of a connected station.
The data link layer contains Media Access Control (MAC) which controls access to the communications media or channel, and the transmission of data packets to and receipt of data packets from the MACs of other stations using individual (MAC) addresses. A data packet is a sequence of data bits on the communications channel which contain the information to be passed from station to station. Connection management (CMT) controls the internal interconnection of the PHY and MAC entities within a station, the external configuration (topology), and establishes the logical connection between adjacent stations.
A DAS is a station, which when its connections type "A" and "B" are connected to the connections type "A" and "B" of another DAS, provides a double loop ring, as shown in FIG. 2. The primary and secondary rings 22 and 24 comprise each of the double loops. A connection type "M" on a WC or DAS/WC forms a "tree" configuration when attached to the connection type "A" of another station, as shown in FIG. 4. Even though a connection type "M" has two physical links, each link forms a part of a single ring. Thus, a DAS/WC station forms a double loop ring with its connections type "A" and "B" and the branches of a tree with its connections type "M." The SAS connects to each branch as a "leaf" of a tree.
Many ring topologies that can be created from SAS, DAS, WC and DAS/WC stations have the undesirable property that two stations may be physically cabled together, i.e., physically connected, but still be unable to exchange MAC layer data packets, as will be shown below. The stations are thus physically connected to each other, but not logically connected, because although the stations are wired together, the internal configuration of the stations prevents data packets from one station on one ring from being received by another station which is not configured on that ring. Thus, stations are considered to be "PHY" connected if and only if they are spanned by a physical cable path where all physical connections in the path are considered usable for data transfer. Stations are logically connected if and only if they can exchange MAC protocol data units (PDUs).
DAS and DAS/WC stations are intended to form double loop rings when attached to other DAS and DAS/WC stations via their connections type "A" and "B." Current Station Management protocols, as described by ANSI subcommittee X3T9.5, "FDDI Station Management (SMT)" in document no. X3T9.5/84-49, 1 August, 1987, do not globally identify a primary or secondary ring and can result in topologies, such as the twisted ring topology of LAN 20 of FIG. 2, if the stations are inadvertently connected incorrectly. Stations connected to DAS/WC stations 28 and 32 are connected to the communications channel forming primary ring 22, but station 36 considers ring 24 to be the primary ring. Stations attached to DAS/WC 36 are therefore unable to communicate, i.e., are not logically connected with stations attached to DAS/WCs 28 and 32 which are configured on the primary ring.
WC or the WC portions of DAS/WC stations are commonly configured as trees, where a connection type "M" of a WC or DAS/WC connects to a connection type "A" of a DAS or DAS/WC. Stations connected as trees do not form double loop rings. Rather, a single ring is intended. LAN 100 of FIG. 4 is a tree comprising two DAS/WC stations which illustrates another illegal topology that can result from improperly connecting stations. SAS 110 is physically connected but not logically connected to the remaining SAS nodes.
For rings to be useful as LANs, the configuration of physical connections must occur automatically as connections are added to or removed from the ring. In the case of FDDI, this has led to the exclusive use of "duplex physical connections" which provide bidirectional communication between all stations in the ring.
Autoconfiguration protocols in use or proposed for ISO PHY and Data Link layers do not detect or correct illegal topologies. Rather, they assume that the network is a legal topology and then correct faults or failures in the LAN.
The spanning tree algorithm, which identifies and corrects (eliminates) illegal topologies, runs in the network layer, and is very complicated, but allows all connection types to be the same and still results in all possible topologies as legal by configuring all networks as trees. Implementation requires too much information to be exchanged by stations to allow the algorithm to run in the MAC layer or Physical layer. In traditional network layer solutions, stations must exchange information with other non-adjacent stations which results in a complex distributed "N-party" algorithm.
The objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the appended claims.